package cn.dapeng.dp;

/**
 * 背包问题
 */
public class KnapsackProblem {

    public static int getMaxValue(int[] v, int[] w, int bagWeight) {
        if (v == null && w == null || v.length != w.length || bagWeight < 0) {
            return 0;
        }
        return process_2(v, w, 0, bagWeight);
    }

    public static int process(int[] v, int[] w, int index, int rest) {
        if (rest < 0) {
            return -1;
        }
        if (index == v.length) {
            return 0;
        }
        //不要商品的逻辑
        int p1 = process(v, w, index + 1, rest);
        // 要商品的逻辑
        int p2 = 0;
        int next = process(v, w, index + 1, rest - w[index]);
        if (next != -1) {
            p2 = v[index] + next;
        }
        return Math.max(p1, p2);
    }

    public static int process_2(int[] w, int[] v, int index, int rest) {
        if (index == v.length) {
            return 0;
        }
        int p1 = process_2(w, v, index + 1, rest);
        int next = rest - w[index];
        int p2 = 0;
        if (next > 0) {
            p2 = v[index] + process_2(w, v, index + 1, next);
        }
        return Math.max(p1, p2);
    }

    public static void main(String[] args) {
        int[] w = {1, 2, 4};
        int[] v = {1500, 2000, 3000};
        System.out.println(getMaxValue(v, w, 4000));
    }
}
